Бинарна претрага
Ако немамо никакве информације о редоследу елемената у низу, једини начин да проверимо да ли се у њему налази неки елемент је да употребимо линеарну претрагу и да редом проверавамо један по један елемент низа. У најгорем случају сваки елемент низа мора бити прегледан, па је сложеност таквог приступа \(O(n)\), где је \(n\) број елемената низа.
Ако је низ елемената сортиран, претрагу је могуће извршити много ефикасније, у сложености \(O(\log{n})\), коришћењем алгоритма бинарне претраге, којим се, услед сортираности низа, одсеца значајан део простора претраге и тако добија на ефикасности. Она се може применити на много сродних проблема.
У основној варијанти, бинарна претрага (БП) служи да се провери да ли сортирани низ елемената садржи неку дату вредност.
Поред овога, БП се може употребити да се пронађе први елемент у сортираном низу који је (било строго, било нестрого) већи или мањи од датог.
У свом најопштијем облику бинарна претрага се користи да се у низу пронађе преломна тачка тј. први елемент који задовољава неки услов (под претпоставком да су елементи поређани тако да у низу прво иду сви елементи који тај услов не задовољавају, а затим они који тај услов задовољавају).
Бинарну претрагу ћемо употребљавати и за оптимизацију, тј. да пронађемо најмању или највећу вредност, која задовољава одређени услов.